/**
 *      Raven     is an high-power, tiny-footprint, open source  
 *                javascript CSS  selector engine.
 * It supports most CSS3 selectors with more to come. It is realeased
 * under the MIT license and may be used by anyone for opensource or 
 * commercial development.  The only request I have, however, is that
 * when asked, I receive credit for the work done here.  Other than that
 * enjoy! :)
 *
 * @author Rick Allen <stoodder@gmail.com>
 *
 * TODO:
 * - Incorporate multiple selectors
 * - finish pseudo selectors
 *   - not()
 *   - contains()
 *   - nth-last-child()
 * - allow for * when doing descendants/child sectors (>, +, ~)
 * - Use a lookup cache table for element relation between eachother
 * - get rid of k in the Raven() method, use shift()?
 */
(function() 
{
    //the root element of this select statement
    var root,
	
    //the current partial select based on values found with the 'subcss' string
    select,
	
    //internal iterator used to push select with new elements
    i,
	
    //internal iterator used to look at elements returned from offspring or descendant
    //lookups
    j,
	
    //the state of the selector, used to determine if at a current subcss lookup an element
    //has already been analyzed, necessary for keeping each element in select unique
    state = 0,
	
    //an array containing all strings found in the css string (anything with '' or ""
    //around it)
    strings,
	
    //another array like strings that captures all equations (such as 2n or 2n-1) between ( )
    equations,
	
    //the subcss we are currently look at (for now this is a reference to the current
    //index in parts
    subcss,
	
    //variable used in selector that represents the tagName to look for (based on what
    //is in the subcss variable
    tagName,
	
    //variable used to determine the class name to look for in the current element
    className,
	
    //variable used to determein and store the id of an element based on the css
    id,
	
    //variable used for storing the name of the attribute to look at in the current element
    attr,
	
    //varibale used to store the attribute value to look at in the current element
    value,
	
    //a variable used to store the descendants returned from an element
    descendants,
	
    //variable used to store the offspring returned from an element
    offspring,
	
    //variable used to hold the current psuedo element
    psuedo,
	
    //variable used to store the length that a loop
    length,
	
    //internal method used to get an element's next sibling element
    _next = function(element)
    {
        var next = element.nextSibling;
        while( !!next )
        {
	  if(next.tagName)
	      return next;
	  next = next.nextSibling;
        }
        return null;
    },
	
    //internal method used to get an element's previous sibling element
    _prev = function(element)
    {
        var prev = element.previousSibling;
        while( !!prev )
        {
	  if(prev.tagName) return prev;
	  prev = prev.previousSibling;
        }
        return null;
    },
	
    //internal method used to get the first child element in the given element
    _first = function(element)
    {
        var first = element.firstChild;
        while( !!first )
        {
	  if( first.tagName ) return first;
	  first = first.nextSibling;
        }
        return null;
    },
	
    //internal method used to get the first child element in the given element
    _last = function(element)
    {
        var last = element.lastChild;
        while( !!last )
        {
	  if( last.tagName ) return last;
	  last = last.previousSibling;
        }
        return null;
    },
	
    //method used to get the index of an element within it's parent
    _index = function(element)
    {
        //have we already looked at this element?
        if( element._raven_state == state )
	  return element._raven_index; //simply pass back the index
		
        for( var child = _first(element.parentNode), index = 0; child; child = _next(child), ++index )
        {
	  child._raven_index = index;
	  child._raven_state = state;
        }
		
        return element._raven_index;
    },
	
    //method used to mimic the break; operator
    _break = function() {
        throw _break;
    },
	
    // Object used to get a method that will filter and format the current subcss part
    _filter = {
        /*----------------------------------------------------------------*/
        //match all descendant elements
        /*----------------------------------------------------------------*/
        "*" : function()
        {
	  return function(element)
	  {
	      if( i < 0 )
	      {
		select = element.all || element.getElementsByTagName("*"),
		i = select.length-1;
		return;
	      }
				
	      //have we already looked at this element?
	      if(element._raven_state == state) return;
				
	      //get the necessary decendants
	      descendants = element.all || element.getElementsByTagName("*"),
	      length = descendants.length;
				
	      for(j = 0; j < length; ++j)
		( select[++i] = descendants[j] )._raven_state = state;
	  }
        },

        /*----------------------------------------------------------------*/
        //match classes
        /*----------------------------------------------------------------*/
        "#" : function()
        {
	  //make it into a regular expression to check
	  id = subcss.slice(1);
			
	  //method used to determine if this element has the requested id
	  return function(element)
	  {
	      if( element.id == id )
		_break( select = [element] );
	  };
        },

        /*----------------------------------------------------------------*/
        //match classes
        /*----------------------------------------------------------------*/
        "." : function()
        {
	  //make it into a regular expression to check
	  className = " " + subcss.slice(1)+  " ";
			
	  return function(element)
	  {
	      if( (" " + element.className + " ").indexOf(className) > -1 )
		select[++i] = element;
	  }
        },

        /*----------------------------------------------------------------*/
        // Match this element and all sub elements, this is used when there
        // is a space between a tag name and a class/id.  since the script
        // divdes the css on the space, we repalce this leading space with
        // an ' character
        /*----------------------------------------------------------------*/
        "'" : function()
        {
	  return function(element)
	  {
	      if( element._raven_state == state) return;
				
	      ( select[++i] = element )._raven_state = state;
				 
	      descendants = element.all || element.getElementsByTagName("*"),
	      length = descendants.length;
				 
	      for( j = 0; j < length; ++j )
		( select[++i] = descendants[j] )._raven_state = state;
	  };
        },

        /*----------------------------------------------------------------*/
        //match children
        /*----------------------------------------------------------------*/
        ">" : function(){
	  //get the tag name (if there is a >, +, or ~ in front)
	  tagName =  subcss.slice(1).toUpperCase();

	  return function (element)
	  {
	      offspring = _first(element);
	      while( !!offspring )
	      {
		if(offspring.tagName == tagName)
		    select[++i] = offspring;
		offspring = _next(offspring);
	      }
	  };
        },

        /*----------------------------------------------------------------*/
        //match next adjacent element
        /*----------------------------------------------------------------*/
        "+" : function()
        {
	  //get the tag name (if there is a >, +, or ~ in front)
	  tagName =  subcss.slice(1).toUpperCase();

	  return function(element)
	  {
	      //get the next sibline
	      var next = _next(element);

	      //if somehting was found and matches the tag, return it
	      if ( !!next && next.tagName == tagName)
		select[++i] = next;
	  };
        },

        /*----------------------------------------------------------------*/
        //match all next siblings
        /*----------------------------------------------------------------*/
        "~" : function()
        {
	  //get the tag name (if there is a >, +, or ~ in front)
	  tagName =  subcss.slice(1).toUpperCase();

	  return function(element)
	  {
	      if(element._raven_state == state)
		return;

	      //get the next sibling
	      var next = _next(element);

	      //look at all next siblings as long as they are valid
	      while ( !!next )
	      {
		//notify that we've already looked at this element,
		//and therefor also every element afterwards
		next._raven_state = state;
					
		//does select tag name match the one we're looing for?
		if (next.tagName == tagName)
		    select[++i] = next;

		//venture on to the next sibling
		next = _next(next);
	      }
	  }
        },

        /*----------------------------------------------------------------*/
        //match psuedo selctors
        /*----------------------------------------------------------------*/
        ":" : function(){
	  psuedo = subcss.toLowerCase();
			
	  //return the specified method based on the psuedo selector
	  return ({
	      //defines the method used to find if select element if the first element of it's parent
	      ':first-child': function (element)
	      {
		//if there is no more previous elements, select is the first one
		if ( !_prev(element) )
		    select[++i] = element; //append the matched element
	      },
				
	      //defined if this element is the last element of it's parent
	      ':last-child': function (element)
	      {
		//if there is no more elements left, select is the last one
		if ( !_next(element) )
		    select[++i] = element; //append the matched elemenr
	      },
				
	      //defines if this element is the only element in its parent
	      ':only-child': function (element) {
		//if select has no siblings, it is the only child
		if ( !_next(element) && !_prev(element) )
		    select[++i] = element; //append the matched element
	      },
				
	      //defines if the given element has no offspring
	      ':empty' : function(element)
	      {
		//this is only empty if no children are found
		if( !_first(element) )
		    select[++i] = element; //append the matched element
	      },
				
	      //selects an element if it is an even element of its parent ( 0 indexed )
	      ':even' : function(element)
	      {
		if( _index(element) % 2 == 0 )
		    select[++i] = element;
	      },
				
	      //selects an element if it is an even element of its parent ( 0 indexed )
	      ':odd' : function(element)
	      {
		if( _index(element) % 2 == 1 )
		    select[++i] = element;
	      },
	      //gets all input type elements
	      ':input' : function(element)
	      {
		if( element.tagName.match(/input|textarea|button/i) )
		    select[++i] = element;
	      },
	      //is this element enabled?
	      ':enabled' : function(element)
	      {
		if( element.tagName.match(/input|textarea|button/i) && !element.disabled )
		    select[++i] = element;
	      },
	      //is this element disabled?
	      ':disabled' : function(element)
	      {
		if( element.tagName.match(/input|textarea|button/i) && !!element.disabled ) //Do we really need this regular expression?
		    select[++i] = element;
	      },
	      //is this element checked?
	      ':checked' : function(element)
	      {
		if( !!element.checked )
		    select[++i] = element;
	      },
	      //is this element not checked?
	      ':unchecked' : function(element)
	      {
		if( ( element.type || "" ).match(/checkbox|radio/i) && !element.checked )
		    select[++i] = element;
	      },
	      ':password' : function(element)
	      {
		//used to grab all of the password fields
		if( ( element.type || "" ).match(/password/i) )
		    select[++i] = element;
	      }
	  //get the specified method in the hash map,
	  }[psuedo]
	  //was this a special selctor such as nth-child()?
	  || (function()
	  {
	      //get the selctor's equation (might be an equation or simple selector for operations like not and has
	      var equation = equations.shift(),
	      a = 0,
	      b = 0;
	      function match_single() {
		a = parseInt( equation.replace(/ /g, "").match(/\(([0-9]+)\)/)[1] || -1 );
	      }
	      function match_multi() {
		var matches = equation.replace(/ /g, "").match(/\((([0-9]+)n[+]?)?([0-9]+)?\)/);
		a = parseInt( matches[2] || 0 ); //get a
		b = parseInt( matches[3] || 0 );
	      }
	      return ({
		':nth-child()' : function()
		{
		    match_multi();
		    var c = a-b; //this is used for the case where we have an+b, it reduces the number of calculations needed
		    //return the matching algorithm based on the equation
		    return ( a > 0 && b > 0 ?
		        //did we match something like #n+# (3n+1)
		        function(element) //append the element id it did
		        {
			  var x = _index(element);
			  if( x >= b && ( x + c ) % a < 1 ) select[++i] = element;
		        }
		        //otherwise did we match something like #n (3n)
		        : ( a > 0 ?
			  function(element) {
			      if( _index(element) % a == 0 ) select[++i] = element;
			  }
			  //lastly just get by index # (3)
			  : 	function(element) {
			      if( _index(element) == b ) select[++i] = element;
			  }
			  ));
		},
		//TODO: This
		/*':nth-last-child()' : function()
		{
		    match_multi();
		},*/
		//gets all elements who's index is greater then the given index
		':gt()': function()
		{
		    match_single();
		    return function(element) {
		        if( _index(element) > a ) select[++i] = element;
		    }
		},
		//gets all elements who's index is less than this index
		':lt()': function()
		{
		    match_single();
		    return function(element) {
		        if( _index(element) < a ) select[++i] = element;
		    }
		},
		//TODO: consider getting rid of these, the same effect can come with a :gt():lt() combo move
		//Gets all elements who's ID is equal to the one given
		':eq()': function()
		{
		    match_single();
		    return function(element) {
		        if( _index(element) == a ) select[++i] = element;
		    }
		},
		//Gets all elements who's ID is not equal to the one given
		':neq()': function()
		{
		    match_single();
		    return function(element) {
		        if( _index(element) != a ) select[++i] = element;
		    }
		}
	      /**
						* TODO:
						* not
						* has
						* nth-last-child
						*/
	      }[psuedo]
	      || function() {
		select = []; _break();
	      }
	      )()
	  })()
	      )
        },

        /*----------------------------------------------------------------*/
        //match attribute selector
        /*----------------------------------------------------------------*/
        "[" : function()
        {
	  //get the index in the subcss of the '=' (if one exists)
	  var index = subcss.indexOf("=");
			
	  //if we didn't find one, simply look to see if we have the attrbute
	  if(index == -1)
	  {
	      //remove the [ and ] on either side of the subcss
	      attr = subcss.slice(1,-1).toLowerCase();
				
	      //pass back the iteration method to use
	      return function (element)
	      {
		//does select attribute exist?
		if ( ( attr == 'class' ? element.className.length > 0  : !!element.getAttribute(attr) ) )
		    select[++i] = element; //append the matched element
	      };
	  }

	  var value = strings.shift(); //get the next string off the strings list
	  value = value.slice(1,-1);
			
	  var func = {
	      //return method, does the attribute start with the given cach value?
	      "^": function (check)
	      {
		return ( check.slice(0, value.length) == value );
	      },
	      //return method, is the value found in a space separated list?
	      "~": function (check)
	      {
		return ( (" " + check + " ").indexOf(" " + value + " ") > -1 );
	      },
	      //return method, is the check value found at the end of the attribute
	      "$": function (check)
	      {
		return ( check.slice(-value.length) == value );
	      },
	      //return method, is the check vaule found anywhere in the attribute?
	      "*": function (check)
	      {
		return ( check.indexOf(value) > -1 );
	      },
	      //return method, is the check value found anywhere in he dash separated attribute
	      "|": function (check)
	      {
		return ( ("-" + check + "-").indexOf("-" + value + "-") > -1 );
	      },
	      //return method, does the check value NOT exist in the aattribute
	      "!": function (check)
	      {
		return ( (check).indexOf(value) == -1 );
	      }
	  }[subcss.charAt(index-1)]; //try to get the correct method
			
	  //if no method found, resort to the default method and get the correct attribute string
	  if( !func )
	  {
	      //set the checking function to default which is to simply compare the element's attribute
	      //against the requested value
	      func = function(check) {
		return (value == check)
	      };
	      attr = subcss.slice(1,-2);
	  }
	  //otherwise get the attribute and string off the special selector character
	  else
	  {
	      attr = subcss.slice(1,-3);
	  }
			
	  //pass back he method to match the attribute based on the given selector
	  return function (element)
	  {
	      //get the attribute of the element
	      if ( func( attr == 'class' ? element.className : element.getAttribute(attr) || "" ) )
		select[++i] = element; //append the matched element
	  };
        }
    };

    /*----------------------------------------------------------------*/
    // Default filtering method to use, the subcss, if valid, will match a tag name
    /*----------------------------------------------------------------*/
    var _defaultFilter = function()
    {
        //get and format the tag name
        tagName = subcss.toUpperCase();
		
        //return the selector method
        return function(element)
        {
	  if( element == root )
	      _break( select = element.getElementsByTagName(tagName) );
				
	  //have we already looked at this element?
	  if(element._raven_state == state) return;
			
	  descendants = element.getElementsByTagName(tagName),
	  length = descendants.length;
			
	  //look over the results and only add those who haven't already been added
	  for(j = 0; j < length; ++j)
	      if( descendants[j]._raven_state != state ) //should be able to get rid of this?
		( select[++i] = descendants[j] )._raven_state = state;
        };
    };

    /**
     * TODO: Incorporate TABLE,TR,TD,w/e Here
     */
    //define the default selector methodology
    function Raven(css, element)
    {
        //make sure the css is a string
        if (typeof css != 'string') return [];

        //get the root 'context' element
        root = ( !element ? document : ( typeof element == 'object' ? element : document.getElementById(element) ) );
		
        //if the element was invalid, pass back a blank array
        if( !root ) return [];
		
        //do we have access to faster internal methods?
        if( root.querySelectorAll )
	  try { return root.querySelectorAll(css); } catch(e) {}
		
        //get all of the strings within the css
        strings = css.match(/("[^"]*")|('[^']*')/g); // get all strings in the css
        css = css.replace(/("[^"]*")|('[^']*')/g, "") //now remove all strings
        equations = css.match(/\([^)]+\)/g); // get all equations ( anything between ( and )
        css = css.replace(/\([^)]+\)/g, "()"); // now remove all of these equations
		
        //start "normalizing" the css string
        css = css	.replace(/\s+(\.|#)/g, "'$1")
        .replace(/([:#.+>[~'])\s*/g, " $1") //put spaces between the necessary characters
        .replace(/\s+/g, " ") //remove all multiple white space
        .replace(/ ?([|^~$*]?=) ?/g, "$1") //if this is an attribtue selector, remove any white space between it.
        .replace(/\[ /, "[") //remove white space between []
        .replace(/ ?(.+) ?/, "$1"); //trim out any leading or trailing space
		
        //if the css is empty, return nothing
        if( css.length == 0 ) return [];
		
        //get each of the parts
        var parts = css.split(" "),
        //reset the subcss parts select iterator
        k = -1;

        //if we're starting with a class or ID just get the descendants, otherwise we must start with the root element
        var result =
        ({
	  "." : function()
	  {
	      return ( root.getElementsByClassName ?
		root.getElementsByClassName( parts[0].slice(++k+1) )
		//otherwise get everything
		: root.all || root.getElementsByTagName("*")
		)
	  },
	  //if we're starting by looking for an ID see if there are any browser specific methods to get an element by id
	  "#" : function()
	  {
	      return  root.all || root.getElementsByTagName("*");
	  }
        }[ css.charAt(0) ]
	  //otherwise just pass back the root element, no intial selections are needed
	  || function()
	  {
	      return [root];
	  }
        )();

        //incremenet through the parts and set the subcss while we can
        while( subcss = parts[++k] )
        {
	  select = [], //reset the subselect
	  i = -1; //reset the sub select iterator

	  try {
	      var filter = ( _filter[ subcss.charAt(0) ] || _defaultFilter )(), //execute operations on the current subcss part and return the filter method
	      size = result.length; //store the length of the currently selected elements for faster loops

	      //iterate through each selected element and apply the current subcss part
	      for( var l = 0; l < size; ++l) filter( result[l] ); //apply the filtering
	  //were we intentionally trying to break out? if not propogate the error
	  } catch (e) {
	      if( e != _break ) throw e;
	  }

	  //store the newly selected nodes as the current selected value
	  result = select;

	  //increment the state (needed for uniqueness of results)
	  ++state;

	  //if nothing is left in the selcect then there is no use in contirnuing
	  if (result.length == 0) break;
        }
	  
        //return our results
        return result;
    }
	
    /**
	* Simple method to always get an array back from a Raven execution.
	*
	* @param {String} css A String css selctor
	* @param {String} root The id of the element to be considered the root elemenet
	* 
	* @return {Array} An array version of the results
	*/
    Raven.array = function( css, root )
    {
        var array = [], //the array we will be pasing back
        raven = Raven(css, root), //find the results
        length = raven.length; //store the length for quicker loops
		
        //if this is already an array don't even bother generating one
        if( Object.prototype.toString.call(raven) == '[object Array]' )
	  return raven;
		
        //generate the array
        for( var i = 0; i < length; ++i )
	  array[i] = raven[i];
		
        //return the result
        return array;
    };
	
    /**
	* Method used to remove the cache within Raven, blank for the non-caching version
	*/
    Raven.clearCache = function() {};
	
    //show the rest of the internets
    window.Raven = Raven;
})();